package jm.algorithm.sort;

import jm.algorithm.tools.Asserts;

/**
 * @Description 二分搜索
 * @date 2022/5/3 11:49
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {2,4,5,6,7,11};
        Asserts.test(BinarySearch.search(arr,4) == 2);
        Asserts.test(BinarySearch.search(arr,2) == 1);
        Asserts.test(BinarySearch.search(arr,12) == 6);
        Asserts.test(BinarySearch.search(arr,8) == 5);
    }

    /**
     * 二分搜索查找 v 在有序数组中位置
     * @param arr 数组
     * @param v 目标值
     * @return 下标位置
     */
    public static int indexOf(int[] arr, int v){
        if (arr == null || arr.length == 0) return -1;
        // end - begin = 元素数量
        int begin = 0;
        int end = arr.length;
        while (begin < end){ // 保证至少有一个元素
            int mid = (end + begin) >> 1;
            if (v < arr[mid]){
                end = mid;
            }else if (v > arr[mid]){
                begin = mid + 1;
            }else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 二分搜索 v 在有序队列中的待插入位置
     * @param arr
     * @param v
     * @return
     */
    public static int search(int[] arr, int v){
        if (arr == null || arr.length == 0) return -1;
        int begin = 0;
        int end = arr.length;
        while (begin < end){ // 当 begin 与 end 相等时退出循环
            int mid = (begin + end) >> 1;
            if (v < arr[mid]){ // 小于时比较内容变为左边
                end = mid;
            }else { // 大于时比较内存变为右边
                begin = mid + 1;
            }
        }
        return begin;
    }
}
